/*
 * @lc app=leetcode.cn id=363 lang=typescript
 *
 * [363] 矩形区域不超过 K 的最大数值和
 */

// @lc code=start
function maxSumSubmatrix(matrix: number[][], k: number): number {
  const rows = matrix.length;
  if (rows === 0) return 0;
  const cols = matrix[0].length;
  let result = Number.NEGATIVE_INFINITY;

  /**
   * @description 计算最大不超过k的子集和
   *
   * 这里用的暴力解法，可以使用其他的有序集合的数据结构，可以降低时间复杂度
   */
  const maxSum = (prefixSum: number[], k: number): number => {
    let max = Number.NEGATIVE_INFINITY;
    const size = prefixSum.length;
    for (let i = 0; i < size; i++) {
      let sum = 0;
      for (let j = i; j < size; j++) {
        sum += prefixSum[j];
        if (sum <= k) {
          max = Math.max(max, sum);
        }
      }
    }
    return max;
  };

  // 遍历左边界
  for (let left = 0; left < cols; left++) {
    // 计算从left开始每一行的前缀和
    const prefixSum = new Array(rows).fill(0);
    // 遍历右边界
    for (let right = left; right < cols; right++) {
      // 按行计算前缀和
      for (let i = 0; i < rows; i++) {
        prefixSum[i] += matrix[i][right];
      }
      //更新结果
      result = Math.max(result, maxSum(prefixSum, k));
    }
  }

  return result;
}
// @lc code=end
